# 给你一个链表数组，每个链表都已经按升序排列。
#  请你将所有链表合并到一个升序链表中，返回合并后的链表。
#  示例 1：
#  输入：lists = [[1,4,5],[1,3,4],[2,6]]
# 输出：[1,1,2,3,4,4,5,6]
# 解释：链表数组如下：
# [
#   1->4->5,
#   1->3->4,
#   2->6
# ]
# 将它们合并到一个有序链表中得到。
# 1->1->2->3->4->4->5->6
#
#
#  示例 2：
#  输入：lists = []
# 输出：[]
#
#  示例 3：
#  输入：lists = [[]]
# 输出：[]
import heapq
from typing import List


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __lt__(self, other):
        return self.val < other.val


class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        """
        归并排序的合并过程
        :param lists:
        :return:
        """
        heap = [head for head in lists if head]
        heapq.heapify(heap)
        mergedHead = ListNode(-1)
        cur = mergedHead
        while heap:
            tmp = heapq.heappop(heap)
            cur.next = tmp
            cur = cur.next
            if tmp.next:
                heapq.heappush(heap, tmp.next)
        return mergedHead.next


if __name__ == "__main__":
    root1 = ListNode(1)
    root1.next = ListNode(4)
    root1.next.next = ListNode(5)

    # print(root1 < root1.next)

    root2 = ListNode(1)
    root2.next = ListNode(3)
    root2.next.next = ListNode(4)

    root3 = ListNode(2)
    root3.next = ListNode(6)
    lists = [root1, root2, root3]
    res = Solution().mergeKLists(lists)
    res = Solution().mergeKLists([None])
    tmp = res
    lst = []
    while tmp:
        lst.append(tmp.val)
        tmp = tmp.next
    print(lst)
